import java.util.LinkedList;

public class SearchTree {
	public static void graphSearchForTreasure(String searchAlgorithm, Maze maze, MazeNodes start) {
		// Create the open and closed lists
		LinkedList<SearchNode> open = new LinkedList<SearchNode>();
		LinkedList<SearchNode> closed = new LinkedList<SearchNode>();
		
		// Compensate for the different way we think about food quanta in graphsearch
		for (MazeNode node : maze.getNodes()) {
			if (node.getType() == MazeNode.Type.START) {
				node.setFood_gain(0);
			}
		}
		
		// Generate the starting path
		CostedPath startPath = new CostedPath(start, new MazeEdges());
		
		// Find the initial h value
		int initialH = 0;
		if (searchAlgorithm.equals("BFS")) {
			initialH = BreadthFirstSearch.generateH(maze, startPath);
		} else if (searchAlgorithm.equals("DFS")) {
			initialH = DepthFirstSearch.generateH(maze, startPath);
		} else if (searchAlgorithm.equals("A")) {
			initialH = AAStar.generateH(maze, startPath);
		}
		
		// Create initial search node and add it to the list of open nodes
		open.addLast(new SearchNode(startPath, initialH));
		
		while (!open.isEmpty()) {
			// Select the next node to expand
			SearchNode currentNode = null;
			if (searchAlgorithm.equals("BFS")) {
				currentNode = BreadthFirstSearch.nextNodeToExpand(open, closed, maze);
			} else if (searchAlgorithm.equals("DFS")) {
				currentNode = DepthFirstSearch.nextNodeToExpand(open, closed, maze);
			} else if (searchAlgorithm.equals("A")) {
				currentNode = AAStar.nextNodeToExpand(open, closed, maze);
			}
			
			// Expand the chosen node
			open.remove(currentNode);
			closed.add(currentNode);
			
			// If we've found the solution, display the expansion and the solution, then return
			if (currentNode.isSolution()) {
				displayExpansion(currentNode, open, closed);
				displaySolution(currentNode);
				return;
			}
			
			// Add the children of currentNode which are not already in the path to open and
			// reorder as required by the chosen search algorithm
			if (searchAlgorithm.equals("BFS")) {
				BreadthFirstSearch.addChildrenToOpen(currentNode, open, closed, maze);
			} else if (searchAlgorithm.equals("DFS")) {
				DepthFirstSearch.addChildrenToOpen(currentNode, open, closed, maze);
			} else if (searchAlgorithm.equals("A")) {
				AAStar.addChildrenToOpen(currentNode, open, closed, maze);
			}
			
			// Display the details for the current node expansion
			displayExpansion(currentNode, open, closed);
			
			// We've finished with the current node. Loop and process the next one.
		}
		
		// If we get here, we didn't find a path.
		System.out.println("ERROR: No path to treasure was found.");
	}
	
	public static void displayExpansion(SearchNode currentNode, LinkedList<SearchNode> open, LinkedList<SearchNode> closed) {
		System.out.println("Order of expansion: " + (closed.size()));
		currentNode.displayNode();
		System.out.println();
		
		if (open.size() <= 10 && closed.size() <= 10) {
			System.out.println("OPEN NODES:");
			for (SearchNode node : open) {
				System.out.println(node.getIdentifier().path.toString());
			}
			
			System.out.println("\nCLOSED NODES:");
			for (SearchNode node : closed) {
				System.out.println(node.getIdentifier().path.toString());
			}
		} else {
			System.out.println("TOO MANY OPEN/CLOSED NODES TO PRINT.");
		}
		System.out.println("\n----------------------------------------\n");
	}
	
	public static void displaySolution(SearchNode solution) {
		CostedPath path = solution.getIdentifier();
		int remainingFQ = path.getFq();
		MazeNode node;
		MazeEdge edge;
		
		System.out.println("SOLUTION FOUND:");
		
		// Display the path
		node = path.path.remove(0);
		System.out.print (node.getName() + " (" + CostedPath.startFQ + ")");
		while (!path.path.isEmpty() && !path.edges.isEmpty()){
			edge = path.edges.remove(0);
			node = path.path.remove(0);
			
			System.out.print(" ---" + edge.getCost() + "---> ");
			
			if (node.getType() != MazeNode.Type.TROLL) {
				System.out.print (node.getName() + " (" + (node.getFood_gain() + node.getFood_consume()) + ")");
			} else {
				System.out.print (node.getName());
			}
		}
		System.out.println();
		
		// Just a quick sanity check - if there's leftover nodes or edges then something is very wrong with the solution
		if (!path.path.isEmpty() || !path.edges.isEmpty()) {
			System.out.println("ERROR: Something has gone terribly wrong. There are leftover nodes/edges after printing the solution.");
		}
		
		// Display the remaining food quanta
		System.out.println("Remaining Food Quanta: " + remainingFQ);
	}


}
